package com.zjsru.oneDay202210;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @Author: CookLee
 * @Date: 2022/10/28
 * 子数组的最小值之和
 *
 * 输入：arr = [3,1,2,4]
 * 输出：17
 * 解释：
 * 子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。
 * 最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。
 *
 */
public class SumSubarrayMins {
    
    int MOD = (int) 1e9 + 7;
    /**
     * 单调栈 + 数学
     *
     * */
    public int sumSubarrayMins(int[] arr) {
        int len = arr.length, ans = 0;
        Deque<Integer> d = new ArrayDeque<>();
        for (int i = 0; i <= len; i++) {
            int t = i < len ? arr[i] : 0;
            while (!d.isEmpty() && arr[d.peekLast()] >= t) {
                int cur = d.pollLast();
                int l = d.isEmpty() ? -1 : d.peekLast();
                int a = cur - l, b = i - cur;
                ans += (long) a * b % MOD * arr[cur] % MOD;
                ans %= MOD;
            }
            d.addLast(i);
        }
        return ans;
    }
    
    /**
     * 暴力 动态规划
     */
    public int sumSubarrayMins2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int n = arr.length;
        long ans = 0;
        // 起点
        for (int i = 0; i < n; i++) {
            int min = arr[i];
            // 终点
            for (int j = i; j < n; j++) {
                min = Math.min(min, arr[j]);
                ans = (ans + min) % MOD;
            }
        }
        return (int) ans;
    }
    
    public static void main(String[] args) {
        SumSubarrayMins sumSubarrayMins = new SumSubarrayMins();
        int[] arr = new int[] {3, 1, 2, 4};
        System.out.println(sumSubarrayMins.sumSubarrayMins(arr));
    }
}
